
/*
回溯
连接：https://leetcode.cn/problems/combination-sum/description/
题目：39. 组合总和

    3. 解法：
    算法思路：
    candidates 的所有元素 互不相同，因此我们在递归状态时只需要对每个元素进⾏如下判断：
    1. 跳过，对下⼀个元素进⾏判断；
    2. 将其添加⾄当前状态中，我们在选择添加当前元素时，之后仍可以继续选择当前元素（可以重复选
    择同⼀元素）。
    • 因此，我们在选择当前元素并向下传递下标时，应该直接传递当前元素下标。
    递归函数设计：void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans,
    vector<int>& combine, int idx)
    参数：target（当前状态和与⽬标值的差），idx（当前需要处理的元素下标）；
    返回值：⽆；
    函数作⽤：向下传递两个状态（跳过或者选择当前元素），找出所有组合使得元素和为⽬标值。
    递归函数流程如下：
    1. 结束条件：
    a. 当前需要处理的元素下标越界；
    b. 当前状态的元素和已经与⽬标值相同；
    2. 跳过当前元素，当前状态不变，对下⼀个元素进⾏处理；
    3. 选择将当前元素添加⾄当前状态，并保留状态继续对当前元素进⾏处理，递归结束时撤销添加操
    作。

*/
//解法1
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int t;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        t = target;
        dfs(candidates,0,0);
        return ret;
    }
    void dfs(vector<int>& candidates,int sum,int pos)
    //pos之前的数字不用考虑了 例如选了2,3 选3开头的时候第二个数字就不能选2，因为3,2_,_... 与 2,3_,_..是一样的
    {
        if(pos == candidates.size()||sum >= t )
        {
            if(sum==t)
                ret.push_back(path);
            return ;
        }
        for(int i =pos;i<candidates.size();i++)
        {
            
            if(sum+candidates[i]>t)
            {
                continue;
            }
            path.push_back(candidates[i]);
            dfs(candidates,sum+candidates[i],i);
            path.pop_back();
        }
    }
};
//解法2
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int t;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        t = target;
        dfs(candidates,0,0);
        return ret;
    }
    void dfs(vector<int>& candidates,int sum,int pos)
    {
        if(pos == candidates.size()||sum >= t )
        {
            if(sum==t)
                ret.push_back(path);
            return ;
        }
        //添加k个pos位置的数字
        for(int k=0;k*candidates[pos]+sum<=t;k++)
        {
            //k==0,表示不添加第pos个数
            if(k) path.push_back(candidates[pos]);
            dfs(candidates,sum+k*candidates[pos],pos+1);
        }
        //回溯，当k个can[pos]添加完毕后，将path中的can[pos]去除
        for(int k=1;k*candidates[pos]+sum<=t;k++)
        {
            path.pop_back();
        }
    }
};